//完全平方数  力扣279
//完全背包   装满背包的最小物品数
class Solution {
public:
	int numSquares(int n) {
		
		vector<long long> dp(n+1,LLONG_MAX);
		//初始化
		dp[0] = 0;
		//递推
		for(int i = 1; i * i <= n; i++)
		{
			for(int j = i*i; j <= n; j++)
			{
				dp[j] = min(dp[j],dp[j-i*i] + 1);
			}
		}
		return dp[n];
		
	}
};
